1. Field of the Invention
The present invention generally concerns cryptology and cryptographic machines, and particularly concerns machines for generating cryptographic keys of indeterminately long length.
2. Description of the Prior Art
2.1 Background to the Present Invention in a Nutshell
The art of secret writing is very ancient, and many different systems have been used throughout history. One of the oldest known ciphers is the Spartan scytale: a transposition cipher based on winding a narrow ribbon of parchment spirally around a cylindrical staff with the message then written on the parchment. The early Greeks used substitution of numerals for letters in some of their systems, while the Romans favored the substitution of one letter for another in the form of the Caesar cipher.
While transposition ciphers seem to have disappeared from use until relatively recently, substitution ciphers continued to evolve in many different ways. With the invention of the printing press, many types of "book ciphers" were devised wherein some book was chosen as the key for the substitutions. Of course, the entire book could be viewed as one long key; thus was born the running key cipher. The running key cipher can be improved dramatically by using a book of random letters, i.e. an incoherent key.
These ideas finally crystallized in the Vernam cipher where a message is bitwise XORed with a random key. Army cryptologist Major Joseph Mauborgne then suggested that the key be used only once, and thus was born the mother of all secret key ciphers, the one-time pad. Subsequently, both William Friedman and Mauborgne arrived at the conclusion that a secure system can be achieved only if an incoherent key is used whose length is at least as long as the message. The theoretical foundation was then laid by C.E. Shannon with the idea of equivocation to provide perfect secrecy. The bad news was that perfection requires a key as long as the message.
The generation, distribution, and storage problems associated with the one-time pad has heretofore made this system impractical for most applications, so the development of small key systems continued. One development was that of block ciphers following Shannon's suggestion of using a "mixing transformation" implemented by applying several rounds of transpositions and substitutions to "diffuse" and "confuse" the statistics of the message.
Another development was the keystream ciphers based on pseudo random number generators. There was temporary interest in using linear shift registers as random number generators until they were proved to be insecure.
The degree of non-linearity required to make small key cipher systems cryptographically secure is currently an open question. A recent approach to the generation of random numbers for purposes of cryptography is to exploit some mathematically intractable problem from number theory in order to gain cryptographic security, and considerable progress has been made with respect to the efficiency of certain methods of random number generation. However, until complexity theory can show decisively that these mathematical problems on which the number generators are based are indeed intractable, a certain wariness will remain.
The present invention will be seen to be concerned with the generation of large, very-large, and indefinitely-large cryptographic keys as suit large key cryptographic systems including, notably but not by way of limitation, the one time pad. The way by which these large cryptographic keys are derived will be seen to be analogous to cryptographic processes themselves.
One analogous class of ciphers that are of special interest to the present invention is the transposition block cipher. The transposition block cipher is performable by pencil and paper, as well as by faster means such as computers. In a transposition block cipher a message is decomposed by letters into fixed length sequences with these sequences consecutively used as the rows in a N.times.M matrix block. A cryptogram is formed by taking the letters from, say, the 3rd column starting from the top, followed by, say, the letters in the 2nd column starting from the bottom, and so on, with this path taken being the key. Many different "flavors" of columnar transposition ciphers were devised, including the so-called ADFGVX system once used by the German Army. The ADFGVX system also utilized substitution.
In order to reach the present invention, it will be seen that (i) the technologically obsolete notion of a small key is discarded, and then (ii) the same ingenuity that Gilbert Vernam used is applied. Namely, or in other words, it will be seen that the present invention calls for the application of a bitwise transposition to a large incoherent key to generate a keystream (subsequently usable for diverse cryptographic processes in the encryption/decryption of data). The bitwise transposition will be seen to include (i) substitution through selected XORings of the "columns", and/or (ii) annihilation through skipping some of the "rows" in each "column", and/or (iii) a method of multiplexing the columns. Finally, as still another essential idea of the present invention, it will be seen that this bitwise transposition is "amorphous", meaning that, complex as the transposition may be in its substitutions and/or annihilations and/or mutiplexing, it is (normally) repetitively recursively performed each time in a different way.
Cryptoanalysis of the amorphous transposition processes gives rise to a mechanical correlation problem. The intractable nature of this problem appears likely to be provable. Even if no proof of the cryptographic security of one or more of the amorphous transposition processes of the present invention is forthcoming, the apparent intractability of these amorphous processes are arguably more attractive than any competing cryptology systems having a supposed intractability of cryptoanalysis based on number theory because the latter systems have an undesirable profundity inherent in their fundamental objects such as the factoring problem. This profundity is continually being revealed as further mathematical research finds new structures which provide means for realizing better algorithms to these problems.
The bitwise transposition processes in accordance with the present invention, on the other hand, will be seen to be, quite intuitively, shapeless--hence the description "amorphous". The mathematical function(s) defined by such an amorphous process(es) will be seen to be so random that the prospects of finding any deep, analyzable, structures in the general amorphous method(s) of the present invention appears to be quite remote.
2.2 Particular Prior Art Cryptography Relevant to the Present Invention
The present invention does not directly concern the encryption or decryption of data. Instead, it concerns the generation of generally long cryptographic keys that are usable by diverse cryptographic processes, including the one time pad.
However, the present invention will be seen to call for the manipulation of a cryptographic key in a like manner, and by like processes, that former cryptographic methods and systems were wont to manipulate (e.g., encrypt or decrypt) data. Since they key manipulation methods of the present invention are (deemed by the Applicant to be) well considered as regards their preservation (and, indeed, even their inducement) of randomness, and amorphousness, in the data sets (i.e., the seed keys) to which they are applied, it will be no surprise that these manipulation methods have a certain correspondence with, and antecedents within, the known methods of cryptography. In some cases the preferred methods, and machines, of the present invention will be seen to constitute variations--arguably even improvements--to certain prior art cryptographic methods of the order of amorphous transforms. Accordingly, understanding certain particular ones of these prior art cryptographic methods will prove useful to placing the present invention in context.
2.3 It is Known to Use of the XOR Function in Cryptography
The present invention will be seen to perform the exclusive or, or XOR, function on the bits of a set. The basic idea of using an incoherent keystream to perform the XOR function on a message dates to the Vernam cipher of 1918.
2.4 Certain Types of Random Permutations Are Known to be Used in Cryptography
The present invention will also be seen to teach the manipulation of the bits of a set by (essentially) random permutations. The use of random permutations in encoding is known. Permutations have been used in voice scrambling systems in both the time and frequency domains. F. Ayoub appears, in his article "Encryption with keyed random permutations", Electronic Letters, Vol 17, 1981, pages 583-585, to have been first to suggest using random permutations for digital data. Ayoub applied an optimal permutation algorithm to minimize the key bits required. Ayoub notes that this method would be useful in substitution-permutation (SP)-type encryption systems.
Ayoub shows, at least implicitly, one part of what Applicant will call a "contracting amorphous process", although Ayoub appears to have only understood permutations in the sense of using such during the encoding of data. Ayoub does not seem to view his permutations as amorphous contraction, i.e. to make the observation that if a pseudo random sequence of bits representing a key is contracted via permutations then the resulting "cipher text" is really a new, secure, key.
Applicant will also be seen to teach the use of a permutation called an "expanding amorphous process". At least some particular forms of expanding amorphous processes are known, as would be expected because of the simplicity of these forms. One early type of an expanding amorphous process is a class of transposition ciphers in which the message is written in matrix form (letter by letter) with the cryptogram formed by taking some path through the matrix to define the letters of the cryptogram. The path taken together with the dimensions of the matrix comprise the cryptographic key of these systems. Other shapes besides rectangles, e.g. triangles, were also used, as well as blocking out certain squares in the template (the irregular columnar cipher). These ciphers were originally performed with pencil and paper so the paths were fairly simple. In one common version, the path went column by column, with the columns permutated, with the letters from the individual columns taken starting from the top, or starting from the bottom, or starting from the top and bottom alternately.
These columnar ciphers will be seen to be similar to the generalized expanding amorphous processes of the present invention. However, the present invention will be seen not only to extend the application of expanding amorphous processes (i.e., to keys as opposed to data), but to add some new "twists". The present invention will be seen to teach each of (i) permuting a matrix of random bits in a feedback mode, (ii) logically complementing some bits and then multiplexing the "columns" via a holdback scheme, and (iii) an amorphous process called "dispersed partitioning".
2.5 State Machines Are Known to be Used in Cryptography
Still furthermore, the present invention will be seen to employ, in one of its embodiments, a state machine. Use of at least some parts of a state machine in keystream generation is known. Specifically, the idea of using a machine index to select a function is discussed in C.E. Shannon's paper "Communication Theory of Secrecy Systems", Bell System Technical Journal, Vol. 28, 1949, pages 656-715. Shannon analyzed ways to combine cipher systems, one basic way being to form a weighted sum consisting of a plurality of different encoding transformations with each transformation assigned a probability of being chosen for use to encode a particular message. From a conceptual standpoint, Applicant's state machine method could be interpreted as a weighted sum of random number generators with a machine index (to be explained in this specification) selecting a function (to be explained). However, Applicant's "function" will be seen to be dynamically redefined at each transition: since the state variables are also used to define this function. Furthermore, Applicant's approach in generating a "garbage index" in order to define a state transition function will deserve careful consideration when later discussed.
As an aside, it may be understood that Shannon's paper is chiefly of theoretical interest dealing in entropy and equivocation. In the course of presenting his theory Shannon did point out some things which could be applied to build a secrecy system, but his paper did not really present any new systems, and to this extent does not relate to Applicant's invention. However, one interesting point that Shannon made was that even a very simple encryption system could be used if the message was first transformed to eliminate all of its redundancies. Unfortunately, such a transformation is in practice extremely difficult, if not impossible, because of the complexity inherent in natural languages.
2.6 Certain Types of Random Number Generators Are Known to be Used in Cryptography
Applicant's method and machine performs random number generation. There are several prominent approaches to random number generation (to form a keystream) that have been taken over the years that are worth mentioning. Linear shift registers have been thoroughly researched. Simple designs exist which have proven "good statistics" and very long cycle lengths. However these sequences are predicable: a small portion yields the whole sequence through a fairly simple process of inverting a matrix formed from this "intercepted" portion. The use of non-linear feedback for shift registers complicates the situation, but the security of such systems is somewhat dubious.
Shannon suggests employing a "mixing transformation" to "diffuse and confuse" the statistics of a message. Applicant's (encryption) of messages (at least directly), but rather of keys. However, Applicant's invention will perform something that could, at least broadly and generically, be called a "mixing transformation". Since most any modern digital circuitry can "throw" a lot a bits around, thereby performing the "mixing" with great vigor, it is useful to understand just how poorly "mixing transformations" have been implemented in the past in order to better assess whether the particular "mixing transformations" taught by Applicant within this specification (even though applied to keys) have cryptographic merit.
European patent number 0035048 shows, in some sense, an early non-linear shift register system. The system is an odd hybrid, comprised of block cipher type "non-affine transformations" in the form of "S" boxes (i.e. substitution tables), strangely, feedback from the message which is used to transform the key matrix. It's inventor, IBM's Horst Feistel, had in 1973 developed a well known block cipher named, of all things, LUCIFER. The banality of LUCIFER soon became apparent with this system duly broken. But its basic structure has been retained, and in fact, this structure was originally due to Shannon's suggestion of employing a "mixing transformation" to "diffuse and confuse" the statistics of a message.
Continuing with the block cipher approach to a "mixing transformation" to "diffuse and confuse", IBM was the main force behind the development of circuits (chips) to perform block ciphers. IBM waived its many patent claims for the particular block cipher derivative later called the "Data Encryption Standard", or DES. DES became the world's first encryption standard around 1978, recently losing its certification in 1986.
Linear congruential generators are another recent development. A proper choice of parameters for the equation x.sub.i +1=(a*x.sub.i +b) mod N yields good random number generators. The Applicant chose this generator as a reasonable "seeding source" as will be seen. However, the numbers produced are not secure. Reference A.M. Frieze, R. Kannan, and J.C. Lagarias, "Linear Congruential Generators do not produce Random Sequences", 25th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Oct. 24-26, 1984, pages 480-484.
However, linear congruential generators can be parameterized to produce random numbers. If a non-linear component is used, a secure sequence results. Here the equation takes the form x.sub.2 mod N (where N is the product of two distinct primes each congruent to 3 mod 4, and x.sub.0 is the quadratic residue mod N) and this is used to generate the sequence x.sub.0, x.sub.1, x.sub.2, . . . from which the bit sequence b.sub.0, b.sub.1, b.sub.2, . . . where b.sub.i =parity(x.sub.i) is formed. Messrs. L. Blum, M. Blum, and M. Shub show in their paper "A Simple Secure Pseudo-Random Number Generator", SIAM Journal of Computing, 1986, pages 364-383 (the main result goes back to about 1982, but many years passed before their paper was published) that the b.sub.i 's are secure.
While Blum's generator (1982) is simple enough, it is rather inefficient since only one bit is emitted for each modular multiplication (n.sup.2 steps) where n is the number of bits in N, typically around several hundred bits. Blum's open question of whether more than a single bit could be securely emitted was answered by the Umesh V. Vazirani and Vijay V. Vazirani in "Efficient and Secure Pseudo-Random Number Generation", 25th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Oct. 24-26, 1984, pages 458-463. The Vazirani's found a way to emit log n bits per multiplication, and their basic proof can be extended to (log n).sub.2 efficiency.
Then, in 1988, Micali and Schnorr came up with a system based on the expression x.sup.d mod N, with their system about as efficient as the simple linear congruential generators. Reference S. Micali and C.P. Schnorr, "Efficient, Perfect Random Number Generators", Lecture Notes in Computer Science, Vol. 403, Advances in Cryptology: Proceedings of CRYPTO 88, Springer-Verlag, 1989, pages 173-198. The "proofs" for the security of these generators are based on certain complexity assumptions. Consequently, if tomorrow a good algorithm for factoring is found, the security of these systems will be invalidated. The continuing research seems to indicate that the present assumptions are pretty good, with the evidence mounting in favor of the security of these systems, but a proof as such has remained elusive and may never be found.
Implementing Micali-Schnorr's generator with a modulus of 224 bits yields 96 bits per multiplication. This about matches the efficiency of an contracting amorphous process using a 128-bit frame feed by using the upper 16-bits of a 32-bit linear congruential generator. The Micali-Schnorr system is probably readily scalable for trade-offs between security and efficiency, and so may thus be superior to Applicant's system--not to mention that Applicant's random number generator is only conjectured to be random.
Yet another idea pertaining to random number generation is that of composite generators in which the outputs of several generators are added together, say, to form a secure keystream. Statistically this appears to be a good idea, although composite generators have not been cryptoanalyzed to Applicant's knowledge. Reference M. Brown and H. Solomon, "On combining pseudorandom number generators", Ann. Statistics, Vol. 7, 1979, pages 691-695. Linear shift registers have also multiplexed together in various ways to form composites, e.g. with one generator used to select the output bit from another generator.
In 1973, the linear shift register generator using characteristic function x.sup.607 +x.sup.334 +1 was shown to have "equidistribution and multidimensional uniformity properties vastly in excess of anything that has yet been shown for conventional congruentially generated sequences". Reference J.P.R Tootill and W.D. Robinson and D.J.Eagle, "An asymptotically random Tausworth Sequence", Journal of the Association for Computing Machinery, Vol. 20, 1973, pages 469-481. This generator has an astronomic period of 2.sup.607 -1. The output is extracted from the full bitstream 23 bits at a time, and then skipping 489 bits, then repeating. The upshot of this is what Applicant calls "contraction", and goes back to 1965 when Tausworth first used a LSR as a generator. Although such jettisoning of bits does falls under the broad category of contraction, a more narrow view of contraction, in particular what the Applicant calls "amorphous contraction", requires an "amorphous" processing which reduces a set of bits to a smaller set in an often simple, but functional, manner.
The keystreams delivered by Applicant's invention will be seen to suitably be used as secret encryption keys, and are thus unsuitable for public key encryption. As an aside, it may be noted for the sake of completeness that public key encryption is a relatively new idea originating with Diffie and Hellman. Reference W. Diffie and M.E. Hellman, "New directions in cryptography", IEEE Trans. Information Theory, IT-22, Vol. 6, Nov. 1976, pages 644-654. Public key encryption is based on asymmetric algorithms. The idea is this. The receiver generates a random number which is then transformed into two keys: a public key and a private key. The public key is insecurely transmitted to the sender. The sender encodes the message with the public key and then insecurely transmits the cryptogram to the receiver. The receiver decodes the cryptogram using the private key. This system is practical provided that a) the problem of decoding the cryptogram with the public key is cryptographically intractable, b) deriving the private key from the public key is cryptographically intractable, c) the generation of the public and private keys is simple, d) encoding with the public key is simple, and e) decoding with the private key is simple.
The only practical public key system that has survived scrutiny is the patented RSA system invented by Rivest, Shamir, and Adleman in 1978. Reference R. Rivest, A. Shamir and L. Adleman, "A method of obtaining digital signatures and public-key cryptosystems", CACM, Vol. 21, No. 2, Feb. 1978, pages 120-128. The encryption formula is C=E(Ks, M)=M.sup.Ks mod N. (The Micali-Schnorr random number generator is a RSA system.) Note that the security of even the DES is suspect. Reference John C. Dvorak, "Inside Track", PC Magazine, Vol. 11, No. 5, Mar. 17, 1992, page 95. Reference also BYTE magazine, May 1993, Vol. 18, No. 6 at page 130.
The Applicant, at various points, employs a permutator to resolve a "permutation selector" into a sequence of permuted indexes. The basic algorithm used follows one due to Moses and Oakford (reference L.E. Moses and R.V. Oakford, "Tables of Random Permutations", Stanford University Press, 1963) and to R. Durstenfeld (reference R. Durstenfeld, 1964, CACM, Vol 7, page 420). The method cited requires one multiplication per permuted index generated. A variant method based on division is reported by Knuth in his series "The Art of Computer Programming", specifically in "Volume 2: Seminumerical Algorithms", Addison-Wesley, second edition, 1981. This later method requires fewer bits in the permutation selector. An optimum permutation algorithm with respect to permutation selector size may be found in S. Even, "Algorithmic Combinatorics", Macmillan, 1973. Minimal selector size results when only the 1's bits of the data are "permutated" by considering only the combinations thereof, at the cost of increased computational complexity.
As a compromise between complexity and selector size, the Applicant has devised a new method based on "hashed division" which generates nearly uniform permutations with only a slightly larger permutation selector than the "division" method, while eliminating the need for multiplication and division.